package basic.study.leetcode;

/**
 * @ClassName Mid152
 * @Description 乘积最大子数组
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/30 11:40
 * @Version 1.0
 */
public class Mid152 {
    class Solution {
        public int maxProduct(int[] nums) {
            int[] dp1 = new int[nums.length];
            int[] dp2 = new int[nums.length];

            dp1[0] = nums[0];
            dp2[0] = nums[0];
            int max = nums[0];

            for (int i = 1; i < nums.length; i++) {
                dp1[i] = Math.max(nums[i], Math.max(dp1[i-1]*nums[i], dp2[i-1]*nums[i]));
                dp2[i] = Math.min(nums[i], Math.min(dp1[i-1]*nums[i], dp2[i-1]*nums[i]));
                max = Math.max(max, dp1[i]);
            }
            return max;
        }
    }
}
